home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Games / reve / README < prev    next >
Encoding:
Text File  |  1995-05-03  |  17.8 KB  |  466 lines
  1.  
  2. /*  @(#)README 1.21 91/11/13
  3.  *
  4.  *  Copyright (C) 1990, 1991 - Rich Burridge & Yves Gallot.
  5.  *  All rights reserved.
  6.  *
  7.  *  Permission is granted to copy this source, for redistribution
  8.  *  in source form only, provided the news headers in "substantially
  9.  *  unaltered format" are retained, the introductory messages are not
  10.  *  removed, and no monies are exchanged.
  11.  *
  12.  *  Permission is also granted to copy this source, without the
  13.  *  news headers, for the purposes of making an executable copy by
  14.  *  means of compilation, provided that such copy will not be used
  15.  *  for the purposes of competition in any othello tournaments, without
  16.  *  prior permission from the authors.
  17.  *
  18.  *  No responsibility is taken for any errors on inaccuracies inherent
  19.  *  either to the comments or the code of this program, but if reported
  20.  *  (see README file), then an attempt will be made to fix them.
  21.  */
  22.  
  23. Reve  -  README  -  November 1991.
  24.  
  25. -----------------------------------------------------------------------
  26. CONTENTS:
  27.  
  28. 1. What is reve?
  29. 2. Getting started.
  30. 3. Strategy used by reve.
  31. 4. Acknowledgements.
  32. -----------------------------------------------------------------------
  33.  
  34. 1. What is reve?
  35. ----------------
  36.  
  37. This is version 1.3.0 of reve (an othello game). This version works under
  38. SunView, XView, X11 and on dumb tty terminals.
  39.  
  40. See the manual pages for a detailed description of the rules of Othello.
  41.  
  42. Two humans can play each other (either locally or remotely), or you can
  43. play against the computer.
  44.  
  45. Reve has various levels of difficulty.
  46.  
  47. You can decide, whether you would like to set a time limit, or a search depth 
  48. limit on the computer move. 
  49.  
  50. The levels of play can be rated approximately as follows:
  51.  
  52. Instant: 
  53.   Beginner level. The search depth is one ply. Even at this level,
  54.   beating reve is not trivial! 
  55.  
  56. 1 Minute/3 Minutes/5 Minutes:
  57.   Intermediate levels. If you often beat reve at the 5 minute level, you
  58.   have probably mastered the basics, and played a lot of games. Interested
  59.   in playing real people in tournaments ? 
  60.  
  61. 10 Minutes:
  62.   Advanced. Beating reve at this level is no piece of cake. 
  63.  
  64. 30 Minutes:  (tournament level)
  65.   More advanced. None of us has beaten reve at this level yet. If you do,
  66.   you should seriously consider participating in your countries national 
  67.   championship. 
  68.  
  69. 60 Minutes: 
  70.   At this level reve looks further ahead than most humans can. If you
  71.   win a game here, send us a transcript, because you have either found
  72.   a serious bug in the algorithm, or your game deserves to be published. 
  73.  
  74. Set Search Depth:  
  75.   Setting the depth is an alternative to using a clock. With a clock, the time
  76.   left decides, how many plys you search for each move. This usually varies
  77.   by one or two plys, depending on where in the game you are, and towards
  78.   the end, it is often worth calculating all the way and then storing some
  79.   moves.
  80.  
  81.   By setting the depth you force the computer to search n plys, no matter where
  82.   in the game you are. There is no clock. This means, that if the depth is set
  83.   to something other than say '0', or whatever you want to use, the computer
  84.   uses the depth, otherwise it will use the time. Or something like that.
  85.   The point of this feature is game analysis. Especially towards the endgame
  86.   you want to be able to let the computer run (for example, over night). Or if
  87.   you know that you usually look 4 plys ahead, you want to play an opponent
  88.   that consistently examines 6 plys. Or you are simply curious what the
  89.   computer would have played had it searched a little further (like situations
  90.   which can only be recognized properly in 6 plys etc. Note, that for each
  91.   additional ply, the compute time increases by about a factor of 4.
  92.  
  93. ----------
  94.  
  95. There is a mailing list for people interested in reve. It is:
  96.  
  97.   reve@Aus.Sun.COM
  98.  
  99. To get added to the list, send a request to:
  100.  
  101.   reve-request@Aus.Sun.COM
  102.  
  103. Early patches are sent to the mailing list, plus active discussion on
  104. ideas for enhancements to reve, plus othello strategy in general.
  105.  
  106. ----------
  107.  
  108. The latest version of reve, recent patches plus an archive of the messages
  109. sent to the reve mailing list are available via anonymous ftp from:
  110.  
  111.    brolga.cc.uq.oz.au     (130.102.128.5)  [Queensland, Australia].
  112.  
  113.    ireq-robot.hydro.qc.ca (131.195.2.130)  [Quebec, Canada].
  114.  
  115. Pick the site nearest to you, and please try to restrict your connections
  116. to outside 9:00am - 5:00pm local time during weekdays.
  117.  
  118. ----------
  119.  
  120. The address where people can get information about tournaments, Othello
  121. Quarterly, and "Othello Brief and Basic' is:
  122.  
  123.         Othello Quarterly
  124.         c/o C.Hewlett
  125.         920 Northgate Ave.
  126.         Waynesboro, VA 22980
  127.         USA
  128.  
  129. 2. Getting started.
  130. -------------------
  131.  
  132. Initially there is no Makefile file present in the reve source directory.
  133. You will need to copy Makefile.dist to Makefile, then adjust accordingly.
  134.  
  135. You need to specify one of the following four options to compile reve:
  136.  
  137.  1/     make sunview      - to make the SunView version.
  138.  2/     make tty          - to make the dumb tty version.
  139.  3/     make x11          - to make the X11 version.
  140.  4/     make xview        - to make the XView version.
  141.  
  142. This should then be followed by a "make install". You might need super-user
  143. permission to do this successfully. The "make install" will concatenate the
  144. two halves of the reve edge stability table together, before installing them.
  145.  
  146. Introduced with reve v1.3, is the ability to play over the network. A network
  147. daemon is used for this, and in order for this to work correctly, a couple of
  148. files need to be edited (as super-user).
  149.  
  150. Add the following line to /etc/services:
  151.  
  152. reve        518/udp
  153.  
  154. [Note if you are running NIS, then you might wish to add this to the
  155.  /etc/services file on the NIS master server, then propogate the change].
  156.  
  157. Add the following line to /etc/inetd.conf:
  158.  
  159. reve    dgram   udp     wait    root    /usr/local/lib/in.reved     in.reved
  160.  
  161. [Note that /usr/local/games/in.reved needs to be replaced with the pathname of
  162.  wherever you've installed the in.reved program].
  163.  
  164. The inetd daemon needs to either be restarted, or forced to re-read its'
  165. configuration file.
  166.  
  167. The manual pages describe the rules of reve in detail.
  168.  
  169. The Makefile compilation details are setup to default to compiling the
  170. SunView version of reve on a Sun4 running SunOS v4.1. Note that there are
  171. various compilation definitions that might need uncommenting if you are
  172. trying to compile and run it on any other machine or graphics environment
  173. or operating system.
  174.  
  175. These are:
  176.  
  177. EDGENAMEFILE - alternate location for the reve edge table.
  178. EDGENAME     - alternate location for the reve edge table.
  179. HASPOLL      - uncomment if you have the poll(2) system call.
  180. HELPNAMEFILE - alternate location for the reve online help file.
  181. HELPNAME     - alternate location for the reve online help file.
  182. NOGETDTAB    - uncomment if you don't have getdtablesize().
  183. NOINDEX      - uncomment if you don't have the index() function.
  184. NOSELECT     - uncomment if your machine doesn't have the select() call.
  185. NO_USLEEP    - uncomment if you don't have the usleep(3) call.
  186. SELTYPE      - uncomment for old select(2) calls.
  187. SIGRET       - uncomment if your signal function expects an integer function.
  188. SYSV         - uncomment if you are running Unix System V.
  189. SVR4LIBS     - uncomment and set, if building under SVR4.
  190. X11R3        - uncomment if you are building the X11 version under X11R3.
  191. X11INCDIR    - X11 only: location of the X11 #include files.
  192. X11LIBDIR    - X11 only: location of the X11 libraries.
  193. XVIEWINCDIR  - XView only: location of the XView #include files.
  194. XVIEWLIBDIR  - XView only: location of the XView libraries.
  195.  
  196. See the Makefile for a detailed description of each of these definitions.
  197.  
  198. If you need to make other changes in order to get reve to compile and run
  199. on your system, please let us know the details (see email addresses below),
  200. and we will try to include them into a future version.
  201.  
  202. See the TODO file for the list of known problems and ideas for future
  203. enhancements.
  204.  
  205. Here are the settings for a variety of machines. Please send additional
  206. machine settings to the address below, to be included in this section.
  207.  
  208.    Type of machine:               Sun 4/65 (color - 1152x900x8).
  209.    O/S release:                   SunOS v4.1.1.
  210.    Version of reve:               X11 (Xlib).
  211.    Uncommented Makefile settings:
  212.  
  213.      EDGENAMEFILE    = $(LIBDIR)/reve.edgetable
  214.      EDGENAME        = -DEDGENAME=\"$(EDGENAMEFILE)\"
  215.      HELPNAMEFILE    = $(LIBDIR)/reve.help
  216.      HELPNAME        = -DHELPNAME=\"$(HELPNAMEFILE)\"
  217.      REVEPROCFILE    = $(LIBDIR)/reve_proc
  218.      REVEPROC        = -DREVEPROC=\"$(REVEPROCFILE)\"
  219.      X11INCDIR       = -I$(OPENWINHOME)/include
  220.      X11LIBDIR       = -L$(OPENWINHOME)/lib
  221.  
  222.    Additional notes:              Uses OpenWindows v3.0(dev).
  223.  
  224.    ---------
  225.  
  226.    Type of machine:               Sun 4/60 (color - 1152x900x8).
  227.    O/S release:                   SVR4 (development platform).
  228.    Version of reve:               X11 (Xlib).
  229.    Uncommented Makefile settings:
  230.  
  231.      EDGENAMEFILE    = $(LIBDIR)/reve.edgetable
  232.      EDGENAME        = -DEDGENAME=\"$(EDGENAMEFILE)\"
  233.      HASPOLL         = -DHASPOLL
  234.      HELPNAMEFILE    = $(LIBDIR)/reve.help
  235.      HELPNAME        = -DHELPNAME=\"$(HELPNAMEFILE)\"
  236.      NOGETDTAB       = -DNOGETDTAB
  237.      NOINDEX         = -DNOINDEX
  238.      NOSELECT        - -DNOSELECT
  239.      NO_TIMEVAL      = -DNO_TIMEVAL
  240.      REVEPROCFILE    = $(LIBDIR)/reve_proc
  241.      REVEPROC        = -DREVEPROC=\"$(REVEPROCFILE)\"
  242.      SYSV            = -DSYSV
  243.      SVR4LIBS        = -lnsl -lsocket -lgen
  244.      X11INCDIR       = -I$(OPENWINHOME)/include
  245.      X11LIBDIR       = -L$(OPENWINHOME)/lib
  246.  
  247.    Additional notes:           Uses OpenWindows v2.0 development libraries.
  248.  
  249.    ---------
  250.  
  251.    Type of machine:               HP Series 9000, model 3[67]0
  252.    O/S release:                   HP-UX release 7.0
  253.    Version of reve:               X11 (Xlib), MIT X11R4 source
  254.    Imakefile settings:
  255.  
  256.      NO_USLEEP       = -DNO_USLEEP
  257.      NOINDEX         = -DNOINDEX
  258.      USRLIBDIR       = /usr/games/lib
  259.  
  260.    ---------
  261.  
  262.    Type of machine:               HP 9000/370.
  263.    O/S release:                   HP-UX 7.0.
  264.    Version of reve:               X11R3.
  265.    Uncommented Makefile configuration settings:
  266.  
  267.      NOGETDTAB       = -DNOGETDTAB
  268.      NOINDEX         = -DNOINDEX
  269.      NO_USLEEP       = -DNO_USLEEP
  270.      X11R3           = -DX11R3
  271.  
  272.    ---------
  273.  
  274.    Type of machine:               DEC 5000/200 (color - 1024x864x8) 
  275.                                   DEC 3100     (mono - 1024x864x1)
  276.    O/S release:                   Ultrix 4.1
  277.                                   Ultrix 4.0
  278.    Version of reve:               X11 (Xlib) (release 4)
  279.    Uncommented Makefile settings:
  280.  
  281.      EDGENAMEFILE    = $(LIBDIR)/reve.edgetable
  282.      EDGENAME        = -DEDGENAME=\"$(EDGENAMEFILE)\"
  283.      HELPNAMEFILE    = $(LIBDIR)/reve.help
  284.      HELPNAME        = -DHELPNAME=\"$(HELPNAMEFILE)\"
  285.      REVEPROCFILE    = $(LIBDIR)/reve_proc
  286.      REVEPROC        = -DREVEPROC=\"$(REVEPROCFILE)\"
  287.      X11INCDIR       = -I$(OPENWINHOME)/include
  288.      X11LIBDIR       = -L$(OPENWINHOME)/lib
  289.  
  290.  
  291. 3. Strategy used by reve.
  292. -------------------------
  293.  
  294. reve is a "classical Othello program", using state of the art othello
  295. strategy. It does not include Bayesian learning [Bill, 1989].
  296.  
  297. References : "A World-Championship-Level Othello Program", Paul S.Rosenbloom,
  298.              Artificial Intelligence 19(1982), 279-320.
  299.              "The Development of a World Class Othello Program", Kai-Fu Lee
  300.              and Sanjoy Mahajan, Art. Int. 43(1990) 21-36.
  301.  
  302. Turning Notes on, displays an evaluation for each computer move. This value
  303. is calculated as follows:
  304.  
  305.   An edgetable is pre-computed. A value is given to each border configuration.
  306.   The average is 0, the mean value about 500.
  307.  
  308.   Then I fix c1 = 312 + 6 * movenumber
  309.              c2 = | 50 + 2 * movenumber   1 <= movenumber <= 25
  310.                   | 75 + movenumber      25 <= movenumber <= 60
  311.              c3 = 99
  312.   ( Iago implementation constants )
  313.  
  314.   then eval = ( c1 * ( edgesnote + Xsquaresnote ) +
  315.                 c2 * currentmobility +
  316.                 c3 * Potentialmobility ) / 1000
  317.  
  318.   mobility = 1000 * ( p - o ) / ( p + o + 2 )
  319.   where p is the evaluation for the player and o for the opponent
  320.  
  321.   p and o are about in the set [ -10, 10 ]
  322.  
  323. In short, a positive number is good for the computer, and a negative numvber
  324. is good for the opponent.
  325.  
  326. Here is a listing of a high level reve vs reve match.
  327.  
  328.                 reve vs reve example.
  329.  
  330.       nt : note reve gives to the position.
  331.       profmax : Depth reve looks forward.
  332.       nbtotnodes : Accumulated number of final nodes evaluated.
  333.  
  334.  1, <C-4>, nt : 0,        profmax : 1,  nbtotnodes : 0
  335.  2, <E-3>, nt : 5107,     profmax : 9,  nbtotnodes : 168236
  336.  3, <F-4>, nt : 31284,    profmax : 9,  nbtotnodes : 459892
  337.  4, <C-5>, nt : 7392,     profmax : 9,  nbtotnodes : 692337
  338.  5, <D-6>, nt : -7392,    profmax : 8,  nbtotnodes : 843560
  339.  6, <C-3>, nt : -29267,   profmax : 8,  nbtotnodes : 1305926
  340.  7, <C-6>, nt : 8574,     profmax : 8,  nbtotnodes : 1461111
  341.  8, <F-5>, nt : -38130,   profmax : 8,  nbtotnodes : 1630589
  342.  9, <E-6>, nt : 7020,     profmax : 8,  nbtotnodes : 1882791
  343. 10, <D-3>, nt : -36894,   profmax : 8,  nbtotnodes : 2136012
  344. 11, <F-3>, nt : 4819,     profmax : 8,  nbtotnodes : 2684014
  345. 12, <F-6>, nt : -4819,    profmax : 7,  nbtotnodes : 3331165
  346. 13, <E-2>, nt : 34302,    profmax : 7,  nbtotnodes : 3539609
  347. 14, <G-4>, nt : -5858,    profmax : 7,  nbtotnodes : 4229607
  348. 15, <G-3>, nt : 5858,     profmax : 6,  nbtotnodes : 4390818
  349. 16, <E-1>, nt : -11790,   profmax : 7,  nbtotnodes : 5137455
  350. 17, <D-2>, nt : 11790,    profmax : 6,  nbtotnodes : 5418077
  351. 18, <F-2>, nt : -46674,   profmax : 6,  nbtotnodes : 5570855
  352. 19, <F-1>, nt : 15648,    profmax : 6,  nbtotnodes : 5766803
  353. 20, <C-1>, nt : -15648,   profmax : 5,  nbtotnodes : 5825491
  354. 21, <D-1>, nt : 52994,    profmax : 7,  nbtotnodes : 6365630
  355. 22, <G-1>, nt : -52994,   profmax : 6,  nbtotnodes : 6556423
  356. 23, <H-5>, nt : 5229,     profmax : 6,  nbtotnodes : 6656104
  357. 24, <H-4>, nt : -3054,    profmax : 7,  nbtotnodes : 7221420
  358. 25, <G-5>, nt : 3054,     profmax : 6,  nbtotnodes : 7313040
  359. 26, <H-6>, nt : -845,     profmax : 7,  nbtotnodes : 7615130
  360. 27, <H-3>, nt : 26592,    profmax : 7,  nbtotnodes : 8026020
  361. 28, <C-2>, nt : -26592,   profmax : 6,  nbtotnodes : 8123951
  362. 29, <H-7>, nt : 5691,     profmax : 6,  nbtotnodes : 8226483
  363. 30, <G-6>, nt : -13265,   profmax : 7,  nbtotnodes : 8301302
  364. 31, <E-7>, nt : 21196,    profmax : 7,  nbtotnodes : 8498532
  365. 32, <D-7>, nt : -19960,   profmax : 7,  nbtotnodes : 8700743
  366. 33, <C-8>, nt : 30104,    profmax : 8,  nbtotnodes : 9672532
  367. 34, <E-8>, nt : -30104,   profmax : 7,  nbtotnodes : 9953691
  368. 35, <D-8>, nt : 63346,    profmax : 8,  nbtotnodes : 10817345
  369. 36, <B-8>, nt : -63346,   profmax : 7,  nbtotnodes : 11038102
  370. 37, <F-7>, nt : 50472,    profmax : 8,  nbtotnodes : 11346042
  371. 38, <C-7>, nt : -11415,   profmax : 8,  nbtotnodes : 11495189
  372. 39, <B-6>, nt : 61958,    profmax : 8,  nbtotnodes : 11783153
  373. 40, <A-5>, nt : 3313,     profmax : 8,  nbtotnodes : 12069521
  374. 41, <B-3>, nt : -585518,  profmax : 9,  nbtotnodes : 12484782
  375. 42, <B-5>, nt : -50483,   profmax : 9,  nbtotnodes : 12680889
  376. 43, <A-6>, nt : -1469439, profmax : 9,  nbtotnodes : 12791711
  377. 44, <A-4>, nt : 2250360,  profmax : 10, nbtotnodes : 13053695
  378. 45, <B-4>, nt : 3,        profmax : 16, nbtotnodes : 13217789
  379. 46, <F-8>, nt : -3,       profmax : 15, nbtotnodes : 13408870
  380. 47, <B-2>, nt : 3,        profmax : 14, nbtotnodes : 13471036
  381. 48, <A-7>, nt : -3,       profmax : 13, nbtotnodes : 13492740
  382. 49, <G-7>, nt : 3,        profmax : 12, nbtotnodes : 13500234
  383. 50, <B-7>, nt : -3,       profmax : 11, nbtotnodes : 13503151
  384. 51, <B-1>, nt : 3,        profmax : 10, nbtotnodes : 13503785
  385. 52, <A-1>, nt : -3,       profmax : 9,  nbtotnodes : 13504016
  386. 53, <A-8>, nt : 3,        profmax : 8,  nbtotnodes : 13504094
  387. 54, <A-2>, nt : -3,       profmax : 7,  nbtotnodes : 13504146
  388. 55, <A-3>, nt : 3,        profmax : 6,  nbtotnodes : 13504159
  389. 56, <H-8>, nt : -3,       profmax : 5,  nbtotnodes : 13504167
  390. 57, <G-8>, nt : 3,        profmax : 4,  nbtotnodes : 13504171
  391. 58, <H-2>, nt : 0,        profmax : 1,  nbtotnodes : 13504171
  392. 59, <G-2>, nt : 0,        profmax : 1,  nbtotnodes : 13504171
  393.  
  394.  
  395. 4. Acknowledgements.
  396. --------------------
  397.  
  398. The previous version of this program was posted to comp.sources.games
  399. under the name othello2. That version was a rework of the SunView
  400. graphics front-end from Ed Falk, Sun Microsystems, CA. It contained
  401. computer strategy and remarks code from Chris Miller.
  402.  
  403. The graphics code was abstracted, and graphics drivers were added for
  404. X11 (Xlib), the XView toolkit, and a dumb tty version.
  405.  
  406. This version has virtually the same graphical interface. The remarks code
  407. has been removed, and the computer strategy is written by Yves Gallot.
  408.  
  409. Thanks to Valerie Haecky for the code for printing reve game boards to
  410. PostScript printers.
  411.  
  412. Thanks to the University of California (Berkeley) for making the talk and
  413. in.talkd programs freely distributable, and therefore providing the basis
  414. for the networked version of reve.
  415.  
  416. Thanks also go to the following for various bug reports, fixes and
  417. suggestions for improvement:
  418.  
  419.   Thomas K. Bischoff,
  420.   Martin Boyer,
  421.   Brett K. Carver,
  422.   Martin Chudley,
  423.   Robert Cohen,
  424.   Scott W. Danielson,
  425.   John Eldredge,
  426.   John Eras,
  427.   Tom Friedel,
  428.   Gordon C. Galligher,
  429.   Krishnamurthy Ganesan,
  430.   Arnold Gill,
  431.   Michael Glad,
  432.   Jacob E. Goodman,
  433.   Valerie Haecky,
  434.   Olaf Heimburger,
  435.   Soren Hein,
  436.   Kjetil Torgrim Homme,
  437.   Peter Johansson,
  438.   Eric R. Jorgensen,
  439.   Norbert Jung,
  440.   Jonathan I. Kamens,
  441.   Gary D. Kline,
  442.   Hugues Leroy,
  443.   Richard K. Lloyd,
  444.   Daniel Edward Lovinger,
  445.   Linton Miller,
  446.   Steve Misrack,
  447.   Keith Moore,
  448.   Alfred Nathaniel,
  449.   D. Hugh Redelmeier,
  450.   John Rosauer,
  451.   Heather Rose,
  452.   Mike Stump,
  453.   W. Mat Waites,
  454.   Mike Wexler,
  455.   Rod Whitby,
  456.   Daniel Yang,
  457.   Andreas Zins.
  458.  
  459. ------------------------------------------------------------------------
  460.  
  461. Suggestions for furthur improvement would be most welcome, plus bugs,
  462. comments and flames.
  463.  
  464. Rich Burridge           richb@Aus.Sun.COM
  465. Yves Gallot             (no net address at present).
  466.